from typing import Optional

from cn.edu.cdu.argorithme.commons.list_node import ListNode


class linked_list_cycle:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        raise NotImplementedError


class solution1(linked_list_cycle):
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        cache = set()
        while head:
            if head in cache:
                return True
            cache.add(head)
            head = head.next
        return False


class solution2(linked_list_cycle):
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return False
        slow, fast = head, head.next
        while slow != fast and fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow == fast
